//
// Created by Lenovo on 2021/3/10.
//


#include <stack>
#include <queue>
#include <vector>
#include <iostream>
#include "tree.h"

BiNode *createBiNode(ElemType data) {
    BiNode *biNode = new (BiNode);
    biNode->data = data;
    biNode->visitCount = 0;
    biNode->lchild = NULL;
    biNode->rchild = NULL;
    biNode->flag = false;
    return biNode;
}

void doCreateTree(BiTree &biTree) {
    std::string ch;
    std::cout << "please input node data: " << std::endl;
    std::cin >> ch;

    if (ch.compare("#") == 0) {
        biTree = NULL;
    } else {
        biTree = createBiNode(ch);
        biTree->data = ch;
        doCreateTree(biTree->lchild);
        doCreateTree(biTree->rchild);
    }
}

BiTree createBiTree() {
    BiTree biTree;
    std::cout << "create tree" << std::endl;
    doCreateTree(biTree);
    return biTree;
}

void visit(BiNode *biNode) {
    if (biNode == nullptr) {
        return;
    }

    std::cout << biNode->data << std::endl;
}

void visit(BiNode *biNode, int traverseType) {
    if (biNode == nullptr) {
        return;
    }

    if (biNode->visitCount == traverseType) {
        std::cout << biNode->data << std::endl;
    }
}

// 先序遍历：根 左 右
// 中序遍历：左 根 右
// 后序遍历：左 右 跟
void orderTraverseTree(BiTree biTree, int traverseType) {
    if (biTree == nullptr) {
        return;
    }

    if (traverseType == 1) visit(biTree);
    orderTraverseTree(biTree->lchild, traverseType);

    if (traverseType == 2) visit(biTree);
    orderTraverseTree(biTree->rchild, traverseType);

    if (traverseType == 3) visit(biTree);
}


// 利用遍历的机制：
// 二叉树节点遍历过程中，有三次经过的机会，
// 第一次经过为先序，即由父节点下来的访问时
// 第二次经过为中序，即由左节点回来的访问时
// 第三次经过为后序，即由右节点回来的访问时
// 增加一个访问标记变量visitCount
void orderTraverseTreeForNot(BiTree biTree, int traverseType) {
    if (biTree == nullptr) {
        return;
    }

    BiNode *pTemp = biTree;
    std::stack<BiNode *> stack;
    while (pTemp != nullptr || !stack.empty()) {
        if (pTemp != nullptr) {
            pTemp->visitCount++;
            visit(pTemp, traverseType);

            stack.push(pTemp);
            pTemp = pTemp->lchild;
        } else {
            pTemp = stack.top();
            pTemp->visitCount++;
            visit(pTemp, traverseType);

            //第三次经过时，这个节点的遍历结束
            if (pTemp->visitCount == 3) {
                stack.pop();

                pTemp->visitCount = 0;
                pTemp = nullptr;
            } else {
                pTemp = pTemp->rchild;
            }
        }
    }
}

//层次遍历实现
//利用队列
//从头节点开始，把子节点放入队列中，
//依次访问队列中的节点，并把节点的子节点放到队列中，
//直到队列为空
void levelTraverseTree(BiTree biTree) {
    BiNode *pTemp = biTree;
    if (pTemp == nullptr) {
        return;
    }

    std::queue<BiNode *> queue;
    queue.push(pTemp);

    while (!queue.empty()) {
        pTemp = queue.front();
        queue.pop();
        visit(pTemp);

        if (pTemp->lchild != nullptr) {
            queue.push(pTemp->lchild);
        }

        if (pTemp->rchild != nullptr) {
            queue.push(pTemp->rchild);
        }
    }
}

void doCopyTree(BiTree tree, BiTree &newTree) {
    if (tree == nullptr) {
        return;
    }

    newTree = createBiNode(tree->data);
    doCopyTree(tree->lchild, newTree->lchild);
    doCopyTree(tree->rchild, newTree->rchild);
}

void copyTree(BiTree tree, BiTree &newTree) {
    //copy
    doCopyTree(tree, newTree);
}

int doGetHighByTree(BiTree tree) {
    if (tree == nullptr) {
        return 0;
    }

    int left = doGetHighByTree(tree->lchild);
    int right = doGetHighByTree(tree->rchild);
    return (left > right ? left : right) + 1;
}

//求解思路：
// 高度为 max(左子树高度，右子树高度) + 1
int getHighByTree(BiTree tree) {

    return doGetHighByTree(tree);
}

int doGetLeaveNodeCountByTree(BiTree tree) {
    if (tree == nullptr) {
        return 0;
    }

    int leftCount = doGetLeaveNodeCountByTree(tree->lchild);
    int rightCount = doGetLeaveNodeCountByTree(tree->rchild);

    if (leftCount == 0 && rightCount == 0) {
        return 1;
    }
    return leftCount + rightCount;
}

//求解思路：
// 叶子节点个数 为 左子树叶子节点个数 + 右子树叶子结点个数
int getLeaveNodeCountByTree(BiTree tree) {
    return doGetLeaveNodeCountByTree(tree);
}

//利用层次遍历，统计每一层的节点个数，取最大值
//重点在于如何知道一层节点结束
// 方法一：加入一个分割节点，每次遍历到该节点表示一层数据遍历完成。
// 方法二：使用一个变量保持一层节点数，然后，弹出这些节点。
int getMaxWidthByTree(BiTree tree) {
    BiNode *pTemp = tree;
    if (pTemp == nullptr) {
        return 0;
    }

    std::queue<BiNode *> queue;
    queue.push(pTemp);

    int maxWidth = 0;
    while (!queue.empty()) {
        int levelSize = queue.size();
        int nowSize = 0;
        while (nowSize++ < levelSize) {
            pTemp = queue.front();
            queue.pop();
            if (pTemp->lchild != nullptr) {
                queue.push(pTemp->lchild);
            }

            if (pTemp->rchild != nullptr) {
                queue.push(pTemp->rchild);
            }
        }
        if (levelSize > maxWidth) {
            maxWidth = levelSize;
        }
    }
    return maxWidth;
}

//利用层次遍历的思想，
//如果遇到空节点，后面还存在数据节点，则为非完全二叉树
bool isCompleteTree(BiTree tree) {
    BiNode *pTemp = tree;
    if (pTemp == nullptr) {
        return false;
    }

    std::queue<BiNode *> queue;
    queue.push(pTemp);
    while (!queue.empty()) {
        bool flag = false;
        int levelSize = queue.size();
        for (int nowSize = 0; nowSize < levelSize; nowSize++) {
            pTemp = queue.front();
            queue.pop();

            if (pTemp != nullptr) {
                if (flag) {
                    return false;
                }

                queue.push(pTemp->lchild);
                queue.push(pTemp->rchild);
            } else {
                flag = true;
            }
        }
    }
    return true;
}